package priv.conceit.study.leetcode.simple.official;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 编号112
 * 路径总和
 * <a href="https://leetcode-cn.com/problems/path-sum/"></a>
 * <p>
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 * <p>
 * 示例：
 * 给定如下二叉树，以及目标和 sum = 22，
 *     5
 *   /   \
 *   4    8
 *  /   /  \
 *  11  13   7
 *  /  \	  \
 * 7    2      1
 * <p>
 * 返回 true
 * 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/16
 */
public class PathSum {

	public static void main(String[] args) {

	}

	public boolean hasPathSum(TreeNode root, int sum) {
		return recursive(root,sum);
	}

	/**
	 * 递归
	 * 从root节点开始，将val累加
	 * 并为left和right 设置默认的flag=false
	 * 只要有一条结果为true,则成立
	 *
	 * 如果左右节点都为空，则计算val是否等于sum
	 * 是则返回true,不再计算
	 * 否则递归继续运行
	 *
	 * @param root
	 * @param sum
	 * @return
	 */
	public boolean recursive(TreeNode root, int sum){
		if(Objects.isNull(root)){
			return Boolean.FALSE;
		}
		boolean left=Boolean.FALSE;
		boolean right=Boolean.FALSE;

		if(Objects.isNull(root.left)&&Objects.isNull(root.right)&&root.val==sum){
			return Boolean.TRUE;
		}

		if(Objects.nonNull(root.left)){
			root.left.val+=root.val;
			left=recursive(root.left,sum);
		}

		if(Objects.nonNull(root.right)){
			root.right.val+=root.val;
			right=recursive(root.right,sum);
		}

		return left||right;
	}


	/**
	 * 广度优先
	 *
	 * 队列实现
	 * 每一层将来自上几级的val的累加值，与当前相加后 进行比较
	 * 相等则true 若当前无则继续进行累加，带入下一次计算
	 *
	 * @param treeNode
	 * @param sum
	 */
	public boolean bfs(TreeNode treeNode, int sum){
		if(Objects.isNull(treeNode)){
			return Boolean.FALSE;
		}

		Queue<TreeNode> treeNodeQueue=new LinkedList<>();
		treeNodeQueue.offer(treeNode);

		while (!treeNodeQueue.isEmpty()){
			//每一层的size需要单独记录，方便出栈
			int size=treeNodeQueue.size();
			for (int i = 0; i <size ; i++) {
				//出栈
				TreeNode cur=treeNodeQueue.poll();
				if(Objects.isNull(treeNode)){
					continue;
				}
				if (cur.val==sum){
					return Boolean.TRUE;
				}else{
					//左右节点不为空 则左右子节点val+cur.val.并入队
					if(Objects.nonNull(cur.left)){
						cur.left.val+=cur.val;
						treeNodeQueue.offer(cur.left);
					}
					if(Objects.nonNull(cur.right)){
						cur.right.val+=cur.val;
						treeNodeQueue.offer(cur.right);
					}
				}

			}

		}

		return Boolean.FALSE;
	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}
